class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>();
        //1.遍历统计每个单词的频率.
        for (String s:words) {
            if (map.containsKey(s)){
                int val = map.get(s);
                map.put(s,val+1);
            }else {
                map.put(s,1);
            }
        }
        //2.建立一个大小为k的小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if (o1.getValue().compareTo(o2.getValue()) == 0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue()-o2.getValue();
            }
        });
        //3.遍历Map,调整堆.
        for (Map.Entry<String,Integer> entry:map.entrySet()) {
            if (minHeap.size() < k){
                minHeap.offer(entry);
            }else {
                //当大于k时,入堆需要进行比较.
                Map.Entry<String,Integer> top = minHeap.peek();
                //当频率相同的时候,字典顺序靠前的入堆.
                if (entry.getValue().compareTo(top.getValue()) == 0){
                    if (entry.getKey().compareTo(top.getKey()) < 0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else {
                    Map.Entry<String,Integer> top1 = minHeap.peek();
                    //当频率不同的时候,比堆顶大的入堆
                    if (entry.getValue().compareTo(top1.getValue()) > 0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        List<String> ret = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> top = minHeap.poll();
            ret.add(top.getKey());
        }
        Collections.reverse(ret);
        return ret;
    }
}